package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/2/25.
 */
public class LC05 {


    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }

        int after = findCurRepeatEndIndex(s, 0);
        String longestStr = s.substring(0, after);
        for (int cur = after; cur < s.length(); ) {
            after = findCurRepeatEndIndex(s, cur);

            String temp = findLongestLoop(s, cur - 1, after);
            if (temp.length() > longestStr.length()) {
                longestStr = temp;
            }

            cur = after;
        }

        return longestStr;
    }

    public int findCurRepeatEndIndex(String str, int cur) {
        int end = cur;
        while (end < str.length() && str.charAt(cur) == str.charAt(end)) {
            ++end;
        }
        return end;
    }

    public String findLongestLoop(String str, int before, int after) {

        while (before >= 0 && after < str.length() && str.charAt(before) == str.charAt(after)) {
            --before;
            ++after;
        }

        return str.substring(before + 1, after);
    }

    public static void main(String[] args) {
        String test = "abbbbacd";
        String test1 = "babad";
        String test2 = "ccd";
        LC05 an = new LC05();
        System.out.println(an.longestPalindrome("babad"));
    }


}
